package cn;
//双向链表
import java.util.Scanner;

public class DuLinkList {
    public DuLNode head;//双向循环链表的头结点
    public DuLinkList(){//双向链表的构造函数，构造只含一个头结点的双向虚幻链表
        head=new DuLNode();//初始化头结点
        head.prior=head;//初始化前驱和后继
        head.next=head;
    
    }
    //从表尾到表头逆向创建双向循环链表的算法，其中n为该双向链表的结点个数
    public DuLinkList(int n) throws Exception{
        this();
        Scanner sc=new Scanner(System.in);
        for(int j=0;j<n;j++){
            insert(0,sc.next());//生成新结点插入到表头
        }
        sc.close();
    }//在带头结点的双向循环链表中的插入操作
    public void insert(int i,Object x)throws Exception{
        DuLNode p=head.next;//初始化，p指向首结点，j为计数器
        int j=0;
        while(!p.equals(head)&&j<i){//寻找插入位置i
            p=p.next;//寻找后继结点
            ++j;//计数器的值加一
        }
        if(j!=i&&p.equals(head)){//i不合法
            throw new Exception("插入位置不合法");//抛出异常
        }
        DuLNode s=new DuLNode(x);//生成新结点
        p.prior.next=s;//将新结点插入到第i个结点的
        s.prior=p.prior;
        s.next=p;
        p.prior=s;
    }//在带头结点的双向循环链表中的删除操作
    public void remove(int i)throws Exception{
        DuLNode p=head.next;//初始化，p指向首结点，j为计数器
        int j=0;
        while(!p.equals(head)&&j<i){
            p=p.next;
            ++j;
        }
        if(j!=i)
        throw new Exception("插入位置不合理");
        p.prior.next=p.next;
        p.next.prior=p.prior;
    }
    public void display(){
        DuLNode node=head.next;//取出带头结点的双向循环链表的首结点
        while(!node.equals(head)){
            System.out.println(node.date+"");//输出节点的数据域
            node=node.next;
        }
        System.out.println();
    }


}
